#include <iostream>
#include <fstream>
#include <sstream>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <limits>

using namespace std;

constexpr int max_int64 = std::numeric_limits<int>::max();

static int four_sum_ways(const vector<vector<int>>& matrix) {
    map<pair<int, int>, pair<int, int>> prev;
    map<pair<int, int>, int> dist;
    set<pair<int, int>> fuck;
    int n = matrix.size();
    int m = matrix[0].size();
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            dist[{i, j}] = max_int64;
            fuck.insert({i, j});
        }
    }
    dist[{0, 0}] = matrix[0][0];
    while (!fuck.empty()) {
        auto compare = [&](const pair<int, int>& a, const pair<int, int>& b) { return dist[a] < dist[b]; };
        auto [i, j] = *min_element(fuck.begin(), fuck.end(), compare);
        fuck.erase({i, j});
        if (i == n - 1 && j == m - 1) break;
        for (auto [di, dj] : vector<pair<int, int>>{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}) {
            int ni = i + di;
            int nj = j + dj;
            if (ni < 0 || ni >= n || nj < 0 || nj >= m) continue;
            if (fuck.find({ni, nj}) != fuck.end()) {
                int new_dist = dist[{i, j}] + matrix[ni][nj];
                if (new_dist < dist[{ni, nj}]) {
                    dist[{ni, nj}] = new_dist;
                    prev[{ni, nj}] = {i, j};
                }
            }
        }
    }
    return dist[{n - 1, m - 1}];
}

int main() {
#if 1
    vector<vector<int>> dp;
    ifstream file ("./83.txt");
    string line;
    while (getline(file, line)) {
        vector<int> v;
        stringstream ss {line};
        string token;
        while (getline(ss, token, ',')) 
            v.push_back(stoi(token));
        dp.push_back(v);
    }
    file.close();
#else
    vector<vector<int>> dp {
        {131, 673, 234, 103, 18},
        {201, 96, 342, 965, 150},
        {630, 803, 746, 422, 111},
        {537, 699, 497, 121, 956},
        {805, 732, 524, 37, 331},
    }; // 2297
#endif
    cout << "matrix: " << dp.size() << " x " << dp[0].size() << endl;
    cout << "min path sum: " << four_sum_ways(dp) << endl;
}

